Search Results

Documents authored by Szykula, Marek

Document
DOI: 10.4230/LIPIcs.MFCS.2018.21
Finding Short Synchronizing Words for Prefix Codes

Authors: Andrew Ryzhikov and Marek Szykula

Published in: LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)

Abstract
We study the problems of finding a shortest synchronizing word and its length for a given prefix code. This is done in two different settings: when the code is defined by an arbitrary decoder recognizing its star and when the code is defined by its literal decoder (whose size is polynomially equivalent to the total length of all words in the code). For the first case for every epsilon > 0 we prove n^(1 - epsilon)-inapproximability for recognizable binary maximal prefix codes, Theta(log n)-inapproximability for finite binary maximal prefix codes and n^(1/2 - epsilon)-inapproximability for finite binary prefix codes. By c-inapproximability here we mean the non-existence of a c-approximation polynomial time algorithm under the assumption P != NP, and by n the number of states of the decoder in the input. For the second case, we propose approximation and exact algorithms and conjecture that for finite maximal prefix codes the problem can be solved in polynomial time. We also study the related problems of finding a shortest mortal and a shortest avoiding word.
Cite as

Andrew Ryzhikov and Marek Szykula. Finding Short Synchronizing Words for Prefix Codes. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 21:1-21:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{ryzhikov_et_al:LIPIcs.MFCS.2018.21,
  author =	{Ryzhikov, Andrew and Szykula, Marek},
  title =	{{Finding Short Synchronizing Words for Prefix Codes}},
  booktitle =	{43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)},
  pages =	{21:1--21:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-086-6},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{117},
  editor =	{Potapov, Igor and Spirakis, Paul and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2018.21},
  URN =		{urn:nbn:de:0030-drops-96037},
  doi =		{10.4230/LIPIcs.MFCS.2018.21},
  annote =	{Keywords: synchronizing word, mortal word, avoiding word, Huffman decoder, inapproximability}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2018.32
Complexity of Preimage Problems for Deterministic Finite Automata

Authors: Mikhail V. Berlinkov, Robert Ferens, and Marek Szykula

Published in: LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)

Abstract
Given a subset of states S of a deterministic finite automaton and a word w, the preimage is the subset of all states that are mapped to a state from S by the action of w. We study the computational complexity of three problems related to the existence of words yielding certain preimages, which are especially motivated by the theory of synchronizing automata. The first problem is whether, for a given subset, there exists a word extending the subset (giving a larger preimage). The second problem is whether there exists a word totally extending the subset (giving the whole set of states) - it is equivalent to the problem whether there exists an avoiding word for the complementary subset. The third problem is whether there exists a word resizing the subset (giving a preimage of a different size). We also consider the variants of the problem where an upper bound on the length of the word is given in the input. Because in most cases our problems are computationally hard, we additionally consider parametrized complexity by the size of the given subset. We focus on the most interesting cases that are the subclasses of strongly connected, synchronizing, and binary automata.
Cite as

Mikhail V. Berlinkov, Robert Ferens, and Marek Szykula. Complexity of Preimage Problems for Deterministic Finite Automata. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 32:1-32:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{berlinkov_et_al:LIPIcs.MFCS.2018.32,
  author =	{Berlinkov, Mikhail V. and Ferens, Robert and Szykula, Marek},
  title =	{{Complexity of Preimage Problems for Deterministic Finite Automata}},
  booktitle =	{43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)},
  pages =	{32:1--32:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-086-6},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{117},
  editor =	{Potapov, Igor and Spirakis, Paul and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2018.32},
  URN =		{urn:nbn:de:0030-drops-96149},
  doi =		{10.4230/LIPIcs.MFCS.2018.32},
  annote =	{Keywords: avoiding word, extending word, extensible subset, reset word, synchronizing automaton}
}
Document
DOI: 10.4230/LIPIcs.STACS.2018.56
Improving the Upper Bound on the Length of the Shortest Reset Word

Authors: Marek Szykula

Published in: LIPIcs, Volume 96, 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)

Abstract
We improve the best known upper bound on the length of the shortest reset words of synchronizing automata. The new bound is slightly better than 114 n^3 / 685 + O(n^2). The Cerny conjecture states that (n-1)^2 is an upper bound. So far, the best general upper bound was (n^3-n)/6-1 obtained by J.-E. Pin and P. Frankl in 1982. Despite a number of efforts, it remained unchanged for about 35 years. To obtain the new upper bound we utilize avoiding words. A word is avoiding for a state q if after reading the word the automaton cannot be in q. We obtain upper bounds on the length of the shortest avoiding words, and using the approach of Trahtman from 2011 combined with the well-known Frankl theorem from 1982, we improve the general upper bound on the length of the shortest reset words. For all the bounds, there exist polynomial algorithms finding a word of length not exceeding the bound.
Cite as

Marek Szykula. Improving the Upper Bound on the Length of the Shortest Reset Word. In 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 96, pp. 56:1-56:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{szykula:LIPIcs.STACS.2018.56,
  author =	{Szykula, Marek},
  title =	{{Improving the Upper Bound on the Length of the Shortest Reset Word}},
  booktitle =	{35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)},
  pages =	{56:1--56:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-062-0},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{96},
  editor =	{Niedermeier, Rolf and Vall\'{e}e, Brigitte},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2018.56},
  URN =		{urn:nbn:de:0030-drops-85160},
  doi =		{10.4230/LIPIcs.STACS.2018.56},
  annote =	{Keywords: avoiding word, Cerny conjecture, reset length, reset threshold, reset word, synchronizing automaton, synchronizing word}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2017.40
Attainable Values of Reset Thresholds

Authors: Michalina Dzyga, Robert Ferens, Vladimir V. Gusev, and Marek Szykula

Published in: LIPIcs, Volume 83, 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)

Abstract
An automaton is synchronizing if there exists a word that sends all states of the automaton to a single state. The reset threshold is the length of the shortest such word. We study the set RT_n of attainable reset thresholds by automata with n states. Relying on constructions of digraphs with known local exponents we show that the intervals [1, (n^2-3n+4)/2] and [(p-1)(q-1), p(q-2)+n-q+1], where 2 <= p < q <= n, p+q > n, gcd(p,q)=1, belong to RT_n, even if restrict our attention to strongly connected automata. Moreover, we prove that in this case the smallest value that does not belong to RT_n is at least n^2 - O(n^{1.7625} log n / log log n). This value is increased further assuming certain conjectures about the gaps between consecutive prime numbers. We also show that any value smaller than n(n-1)/2 is attainable by an automaton with a sink state and any value smaller than n^2-O(n^{1.5}) is attainable in general case. Furthermore, we solve the problem of existence of slowly synchronizing automata over an arbitrarily large alphabet, by presenting for every fixed size of the alphabet an infinite series of irreducibly synchronizing automata with the reset threshold n^2-O(n).
Cite as

Michalina Dzyga, Robert Ferens, Vladimir V. Gusev, and Marek Szykula. Attainable Values of Reset Thresholds. In 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 83, pp. 40:1-40:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{dzyga_et_al:LIPIcs.MFCS.2017.40,
  author =	{Dzyga, Michalina and Ferens, Robert and Gusev, Vladimir V. and Szykula, Marek},
  title =	{{Attainable Values of Reset Thresholds}},
  booktitle =	{42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)},
  pages =	{40:1--40:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-046-0},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{83},
  editor =	{Larsen, Kim G. and Bodlaender, Hans L. and Raskin, Jean-Francois},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2017.40},
  URN =		{urn:nbn:de:0030-drops-81220},
  doi =		{10.4230/LIPIcs.MFCS.2017.40},
  annote =	{Keywords: Cerny conjecture, exponent, primitive digraph, reset word, synchronizing automaton}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact